package com.nowc.week.w103_ak;

import java.io.*;

public class d {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine());
            String s = br.readLine();
            int good = 0;
            for (int i = 1; i < n; i++) {
                int x = s.charAt(i) - '0';
                int y = s.charAt(i - 1) - '0';
                if ((x ^ y) == 1) {
                    good++;
                }
            }
            if (good >= 3) {
                out.println(0);
            } else {
                if (n >= 5) {
                    out.println((3 - good + 1) / 2);
                } else {
                    int ans = n;
                    for (String t : new String[] { "1010", "0101" }) {
                        int cur = 0;
                        for (int i = 0; i < n; i++) {
                            cur += (s.charAt(i) - '0') != (t.charAt(i) - '0') ? 1 : 0;
                        }
                        ans = Math.min(ans, cur);
                    }
                    out.println(ans);
                }
            }
        }
        out.flush();
        out.close();
        br.close();
    }
}